package vip.zhenzicheng.algorithm.sort;

import static vip.zhenzicheng.algorithm.util.ArrayUtils.*;

/**
 * 堆排序，满二叉树性质：任意一个root节点的左节点为2*k+1，右节点为2*(k+1)
 *
 * @author zhenzicheng
 * @date 2022-06-08 14:59
 */
public class HeapSort {

  private static int N; // 记录数组长度

  public static void main(String[] args) {
    int[] randomArray = getRandomArray(10, 20);
    headSort(randomArray);
    printArray(randomArray);
  }

  public static void headSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    N = arr.length;
    // 构建一个最大堆
    buildMaxHeap(arr);
    // 循环将堆的根节点(最大值/最小值)与未排序数据末尾交换，然后重新调整为最大最堆
    while (N > 0) {
      swap(arr, 0, N - 1); // 首先将根节点与尾节点数据交换
      N--; // 交换后移除最后一个节点，即已经选择出了一个最大值或最小值
      adjustHeap(arr, 0); // 调整为最大堆
    }
  }

  // 将数组构建一个最大堆格式
  public static void buildMaxHeap(int[] arr) {
    // 从最后一个非叶子节点开始向上构造最大堆
    for (int i = (N / 2 - 1); i >= 0; i--) {
      adjustHeap(arr, i);
    }
  }

  public static void adjustHeap(int[] arr, int i) {
    int maxIndex = i;
    int left = 2 * i + 1;
    int right = 2 * (i + 1);

    if (left < N && arr[left] > arr[maxIndex]) {
      maxIndex = left;
    }
    if (right < N && arr[right] > arr[maxIndex] && arr[right] > arr[left]) {
      maxIndex = right;
    }
    if (maxIndex != i) { // 当前父节点不是刚才选出的最大值，就交换并重新调整
      swap(arr, maxIndex, i);
      adjustHeap(arr, maxIndex);
    }
  }

}
